package TwoPointers;


/**
 * 42.接雨水
 * 困难
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 */
public class trap {
    /**
     * hot100一刷
     */
    public int trap(int[] height) {
        int[] left = new int[height.length];//左边比他大的最大的元素
        int[] right = new int[height.length];//右边比他大的最大的元素
        int maxleft = height[0];
        int maxright = height[height.length - 1];
        left[0] = height[0];
        right[height.length - 1] = height[height.length - 1];
        for (int i = 1; i < height.length; i++) {
            maxleft = Math.max(maxleft, height[i]);
            left[i] = maxleft;
        }
        for (int i = height.length - 2; i >= 0; i--) {
            maxright = Math.max(maxright, height[i]);
            right[i] = maxright;
        }
        int sum = 0;
        for (int i = 0; i < height.length; i++) {
            sum += Math.min(left[i], right[i]) - height[i];
        }
        return sum;
    }

    /**
     * hot100二刷
     */
    class Solution {
        public int trap(int[] height) {
            int n = height.length;
            int sum = 0;
            int leftmax[] = new int[n];
            int rightmax[] = new int[n];
            leftmax[0] = height[0];
            rightmax[n - 1] = height[n - 1];
            for (int i = 1; i < n; i++) {
                leftmax[i] = Math.max(height[i], leftmax[i - 1]);
            }
            for (int i = n - 2; i >= 0; i--) {
                rightmax[i] = Math.max(height[i], rightmax[i + 1]);
            }
            for (int i = 0; i < n; i++) {
                sum += Math.min(leftmax[i], rightmax[i]) - height[i];
            }
            return sum;
        }
    }

}
